package _11_整理题目._4_动态规划._买卖股票;

/**
 * https://leetcode.cn/problems/best-sightseeing-pair/
 * https://leetcode.cn/problems/best-sightseeing-pair/solution/xue-xi-bi-ji-dpji-qiao-ru-men-zui-jia-gu-yjt0/
 *
 * 给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，
 * 并且两个景点 i 和 j 之间的 距离 为 j - i。
 * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，
 * 也就是景点的评分之和 减去 它们两者之间的距离。
 * 返回一对观光景点能取得的最高分。
 *
 * 1、暴力循环 n^2
 * 2、动态规划
 *      dp[i]
 */
public class _01_最佳观光组合 {

    public int maxScoreSightseeingPair1(int[] values) {
        int n = values.length;
        int max = 0;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                max = Math.max(max, values[i]+values[j]+i-j);
            }
        }
        return max;
    }


}
